package com.peng.leetcode.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * BinaryTreePaths1
 * 257. 二叉树的所有路径
 * https://leetcode.cn/problems/binary-tree-paths/
 * <p>
 * Created on 2022/11/27
 *
 * @author lupeng
 */
public class BinaryTreePaths1 {

    List<List<Integer>> ans = new ArrayList<>();

    ArrayDeque<Integer> q = new ArrayDeque<>();

    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root);
        List<String> res = new ArrayList<>();
        for (List<Integer> l : ans) {
            StringBuilder val = new StringBuilder();
            for (int i = 0; i < l.size(); i++) {
                val.append(l.get(i));
                if (i != (l.size() - 1)) {
                    val.append("->");
                }
            }
            res.add(val.toString());
        }
        return res;
    }

    private void dfs(TreeNode r) {
        if (r == null) {
            return;
        }
        q.addLast(r.val);
        if (r.left == null && r.right == null) {
            ans.add(new ArrayList<>(q));
        }
        dfs(r.left);
        dfs(r.right);
        q.pollLast();
    }
}
